#pragma once
#include <unordered_map>
#include <mutex>
#include <memory>
#include <cmath>
#include <iostream>
#include "KICachePolicy.hpp"

template <typename Key, typename Value>
struct LfuNode
{
    std::weak_ptr<LfuNode<Key, Value>> m_pre;
    std::shared_ptr<LfuNode<Key, Value>> m_next;
    Key m_key;
    Value m_value;
    int m_freq;
    
    LfuNode() : m_freq(1), m_next(nullptr)
    {}

    LfuNode(const Key& key, const Value& value) : m_key(key), m_value(value), m_freq(1), m_next(nullptr)
    {}
};

template <typename Key, typename Value>
class FreqList
{
private:
    std::shared_ptr<LfuNode<Key, Value>> m_head;
    std::shared_ptr<LfuNode<Key, Value>> m_tail;

    void initFreqList()
    {
        m_head = std::make_shared<LfuNode<Key, Value>>();
        m_tail = std::make_shared<LfuNode<Key, Value>>();
        m_head->m_next = m_tail;
        m_tail->m_pre = m_head;
    }
public:
    FreqList()
    {
        initFreqList();
    }

    void addNode(std::shared_ptr<LfuNode<Key, Value>> node)
    {
        if (!node)
        {
            return;
        }
        node->m_pre = m_tail->m_pre;
        node->m_next = m_tail;
        m_tail->m_pre.lock()->m_next = node;
        m_tail->m_pre = node;
    }

    void removeNode(std::shared_ptr<LfuNode<Key, Value>> node)
    {
        if (!node)
        {
            return;
        }
        node->m_pre.lock()->m_next = node->m_next;
        node->m_next->m_pre = node->m_pre;
        node->m_next = nullptr;
    }

    std::shared_ptr<LfuNode<Key, Value>> getFirstNode() const
    {
        return m_head->m_next;
    }

    bool isEmpty() const
    {
        return m_head->m_next == m_tail;
    }
};

template <typename Key, typename Value>
class LFUCache : public KICachePolicy<Key, Value>
{
public:
    LFUCache(int capacity, int _maxAverageNum = 1000000) : min_freq(INT8_MAX), m_capacity(capacity), maxAverageNum(_maxAverageNum)
    , curAverageNum(0), curTotalNum(0)
    {}

    void put(const Key& key, const Value& value)
    {
        if (m_capacity <= 0)
        {
            return;
        }
        std::lock_guard<std::mutex> lck(mtx);
        auto it = hashNode.find(key);
        if (it != hashNode.end())
        {
            it->second->m_value = value;
            getInternal(it->second);
            return;
        }
        putInternal(key, value);
    }

    bool get(const Key& key, Value& value)
    {
        std::lock_guard<std::mutex> lck(mtx);
        auto it = hashNode.find(key);
        if (it != hashNode.end())
        {
            value = it->second->m_value;
            getInternal(it->second);
            return true;
        }
        return false;
    }

    Value get(const Key& key)
    {
        Value value;
        get(key, value);
        return value;
    }

    void purge()
    {
        // 清空缓存，回收资源
        hashNode.clear();
        hashFreqList.clear();
    }
private:
    void putInternal(const Key& key, const Value& value)
    {
        // 满了，移除频次最低且最久未使用的节点
        if (hashNode.size() == m_capacity)
        {
            auto node = hashFreqList[min_freq]->getFirstNode();
            deleteFromFreqList(node);
            hashNode.erase(node->m_key);
            decreaseFreqNum(node->m_freq);
        }
        std::shared_ptr<LfuNode<Key, Value>> node = std::make_shared<LfuNode<Key, Value>>(key, value);
        addToFreqList(node);
        hashNode[key] = node;
        min_freq = std::min(min_freq, 1);
        addFreqNum();
    }

    void getInternal(std::shared_ptr<LfuNode<Key, Value>> node)
    {
        int& freq = node->m_freq;
        // 从原有频次的链表中删除
        deleteFromFreqList(node);
        ++freq;
        // 加入到新频次的链表中
        addToFreqList(node);
        // 如果之前是最小频次链表中的唯一一个节点，则更新min_freq
        if (freq - 1 == min_freq && hashFreqList[min_freq]->isEmpty())
        {
            ++min_freq;
        }
        addFreqNum();
    }

    void addToFreqList(std::shared_ptr<LfuNode<Key, Value>> node)
    {
        if (!node)
        {
            return;
        }
        int freq = node->m_freq;
        auto it = hashFreqList.find(freq);
        if (it == hashFreqList.end())
        {
            hashFreqList[freq] = new FreqList<Key, Value>();
        }
        hashFreqList[freq]->addNode(node);
    }

    void deleteFromFreqList(std::shared_ptr<LfuNode<Key, Value>> node)
    {
        if (!node)
        {
            return;
        }
        int freq = node->m_freq;
        hashFreqList[freq]->removeNode(node);
    }

    void addFreqNum()
    {
        ++curTotalNum;
        if (hashNode.empty())
        {
            curAverageNum = 0;
            return;
        }
        else
        {
            curAverageNum = curTotalNum / hashNode.size();
        }
        if (curAverageNum > maxAverageNum)
        {
            // 处理每个节点的频次
            handleOverFreq();
        }
    }

    void decreaseFreqNum(int num)
    {
        curTotalNum -= num;
        if (hashNode.empty())
        {
            curAverageNum = 0;
        }
        else
        {
            curAverageNum = curTotalNum / hashNode.size();
        }
    }

    void handleOverFreq()
    {
        int tmpFreq = maxAverageNum / 2;
        for (auto& pair : hashNode)
        {
            auto node = pair.second;
            deleteFromFreqList(node);
            node->m_freq -= tmpFreq;
            if (node->m_freq < 1)
            {
                node->m_freq = 1;
            }
            addToFreqList(node);
        }
        // 更新最小频次
        updateMinFreq();
    }

    void updateMinFreq()
    {
        min_freq = INT8_MAX;
        for (const auto& e : hashFreqList)
        {
            if (e.second && !e.second->isEmpty())
            {
                min_freq = std::min(min_freq, e.first);
            }
        }
        if (min_freq == INT8_MAX)
        {
            min_freq = 1;
        }
    }
private:
    std::unordered_map<Key, std::shared_ptr<LfuNode<Key, Value>>> hashNode;
    std::unordered_map<int, FreqList<Key, Value>*> hashFreqList;
    int min_freq; 
    int m_capacity;
    std::mutex mtx;
    int curAverageNum;
    int maxAverageNum;
    int curTotalNum;
};